package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

/**
 * 先序后序还原树 see 889 105 106
 *
 * @author tzp
 * @since 2020/9/11
 */
public class LC889 implements TreeProblem {

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 5, 3, 6, 7};
        int[] post = {4, 5, 2, 6, 7, 3, 1};
        TreeNode treeNode = new LC889().constructFromPrePost(pre, post);
        System.out.println(treeNode);
    }

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if (pre == null || pre.length == 0 || post == null || post.length == 0) {
            return null;
        }
        int l = pre.length;
        return re(pre, post, 0, l - 1, l - 1, 0);
    }

    public TreeNode re(int[] pre, int[] post, int p1s, int p1e, int p2s, int p2e) {
        TreeNode root = new TreeNode(pre[p1s]);
        if (p1s == p1e) {
            return root;
        }

        if (pre[p1s + 1] == post[p2s - 1]) {//单叉
            TreeNode child = re(pre, post, p1s + 1, p1e, p2s - 1, p2e);
            root.left = child;
        } else {
            int lf = pre[p1s + 1];//2
            int rt = post[p2s - 1];//3
            int rtInPre = findA(pre, rt);
            int lfInPost = findA(post, lf);
            root.left = re(pre, post,
                    p1s + 1, rtInPre - 1,
                    lfInPost, p2e);
            root.right = re(pre, post,
                    rtInPre, p1e,
                    p2s - 1, lfInPost + 1);
        }
        return root;
    }

    public int findA(int[] post, int e) {
        for (int i = 0; i < post.length; i++) {
            if (post[i] == e) {
                return i;
            }
        }
        return -1;
    }
}
